package com.shawn.leetcode.dynamicprogramming.minPathSum;

import java.util.Arrays;

public class SolutionOne implements Solution {

	@Override
	public int minPathSum(int[][] grid) {
		int[][] minArr = new int[grid.length][grid[0].length];
		minArr[grid.length - 1][grid[0].length - 1] = grid[grid.length - 1][grid[0].length - 1];
		for(int i = grid.length - 1; i > 0; i--){
			for(int j = grid[i].length - 1; j > 0; j--){
				if(grid[i - 1][j] <=  grid[i][j - 1]){
					minArr[i - 1][j] = minArr[i][j] + grid[i - 1][j];
				}else{
					minArr[i][j - 1] = minArr[i][j] + grid[i][j - 1];
				}
			}
		}
		return minArr[1][1];
	}

	public static void main(String[] args) {
		SolutionOne min = new SolutionOne();
		int[][] grid = {
			{1, 3, 1},
			{1, 5, 1}
		};
		System.out.println(min.minPathSum(grid));
//		for (int i = 0; i < grid.length ; i++) {
//			for (int j = 0; j < grid[i].length ; j++) {
//				System.out.print(grid[i][j] + ",");
//			}
//			System.out.println();
//		}
	}
}
